package merisis.spindle;

import java.nio.ByteBuffer;

import merisis.util.WordArrayMedia;

public class AnchorPointGraph {

	private WordArrayMedia media;

	private int HEAD_LEN = 2;

	public AnchorPointGraph(WordArrayMedia media) {
		this.media = media;
	}

	public long reach(long... arrows) {

		int len = arrows.length;

		ByteBuffer cell = media.allocate(len + HEAD_LEN);

		/**
		 * +-----------+----------+-------+-----+-------+ | arrow_num | desc_ptr |
		 * arw_0 | ... | arw_n | +-----------+----------+-------+-----+-------+
		 */
		// The head of cell
		cell.putLong((len << 1) + 1);

		// The body of cell
		for (int i = 0; i < len; i++) {

			long arrow = arrows[i];
			if ((media.read(arrow) & 0x1) != 0) {

				cell.putLong(arrows[i] << 1);
			} else {

				long k = arrow;
				while (k >= 0) {

					// find the initial position of cell
					if ((media.read(k) & 0x1) != 0) {

						cell.putLong(k << 1);
						break;
					}

					k--;
				}
			}
		}

		long cellpos = media.append(cell);

		return cellpos;
	}

	public int readOpaqueObject(ByteBuffer buf, long start, long len) {
		return 0;
	}

	public void writeOpaqueObject(ByteBuffer buf) {

	}

	public void connect(Spindle spdl) {

	}

	public void disconnect() {

	}

	public boolean connective(long proximal, long distal) {

		proximal = distalCellPtr(proximal);
		distal = alignOwnCellPtr(distal);
		return isConnectiveCell(proximal, distal);
	}

	public boolean proofed(long proximal, long distal) {
		return false;
	}

	public long[] tract(long proximal, long distal) {

		proximal = distalCellPtr(proximal);
		distal = alignOwnCellPtr(distal);

		long plword = media.read(proximal);
		int cellSize = (int) (plword >>> 1);
		long plIdx = proximal + 1;
		long plEnd = proximal + cellSize;
		long[] matched = new long[cellSize];
		int rpos = 0;
		while (plIdx <= plEnd) {

			long candidate = (media.read(plIdx) >>> 1);
			if (isConnectiveCell(candidate, distal)) {
				matched[rpos++] = candidate;
			}

			plIdx++;
		}

		if (rpos == 0)
			return null;

		if (rpos == cellSize)
			return matched;

		long[] shrunk = new long[rpos];
		System.arraycopy(matched, 0, shrunk, 0, rpos);
		return shrunk;
	}

	private long distalCellPtr(long ptr) {

		long word = media.read(ptr);
		if ((word & 0x1) == 0) {
			long k = (word >>> 1);
			do {
				word = media.read(k);
				k = (word >>> 1); // go far
			} while ((word & 0x1) == 0 && k > 0);
			if (k == 0)
				return 0;
			return k;
		} else
			return ptr;
	}

	private long alignOwnCellPtr(long ptr) {

		long word = media.read(ptr);
		if ((word & 0x1) == 0) {
			long k = (word >>> 1);
			do {
				word = media.read(k);
				k--; // young brothers
			} while ((word & 0x1) == 0 && k > 0);
			if (k == 0)
				return 0;

			return k;
		} else
			return ptr;
	}

	private boolean isConnectiveCell(long proximal, long distal) {

		if (proximal <= distal)
			return false;

		long cellsize = media.read(proximal) >>> 1;
		long youngest = proximal + 1;
		long eldest = proximal + cellsize;

		long start = searchNearestElderArrow(youngest, eldest, distal);

		do {
			long ontocell = media.read(start) >>> 1;
			if (ontocell == distal)
				return true;

			// exploit the onto-cell
			if (isConnectiveCell(ontocell, distal)) {
				return true;
			}

			start++; // the elder brother.
		} while (start <= eldest);

		return false;
	}

	private long searchNearestElderArrow(long young, long eld, long distal) {

		while (young <= eld) {
			long mid = (young + eld) >>> 1;

			long midVal = (media.read(mid) >> 1);

			if (midVal < distal)
				young = mid + 1;
			else if (midVal > distal)
				eld = mid - 1;
			else
				return mid; // key found
		}

		return young;
	}
}
